【题解】 Qtree3 LCT luoguP4116 | Qiuly's blog!

【题解】 Qtree3 LCT luoguP4116

Posted on | Edited on | In | Comments:

第一个操作显然是不要考虑的……

考虑第二个操作怎么办(实际上是超级easy的)

每个节点维护一个值sum，表示 $Splay$ 中它子树的和，每个点的权值为1(黑)0(白)。

对于这个操作，我们可以先 $split(1,x)$ ，现在x是这个 $Splay$ 的根。我们将要找的就是这颗 $Splay$ 中深度最小且为黑点的节点。

找Answer之前先特判一下s[x]是否大于0，如果为0，直接跳过即可。

不然进入循环，分三种情况：

  • 1.如果s[ch[x][0]]大于0，说明有更优的答案(左子树深度小于x)，x=ch[x][0]。
  • 2.否则，如果x本身就是黑点，那么x就是答案了，直接break。
  • 3.不然，如果x到1的节点都是白色，那就只能去x的右子树找了，x=ch[x][1]。

退出循环时x即为答案，输出即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define RI register int
#define A printf("A") 
using namespace std;
const int N=1e5+2;
int n,m,f[N],s[N],v[N],r[N],ch[N][2];
template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}
inline int chk(int x){return ch[f[x]][1]==x;}
inline int isroot(int x){return ch[f[x]][0]==x||ch[f[x]][1]==x;}
inline void pushup(int x){s[x]=s[ch[x][0]]+s[ch[x][1]]+v[x];}
inline void pushdown(int x){
    if(!r[x])return;r[x]=0;
    r[ch[x][0]]^=1,r[ch[x][1]]^=1,swap(ch[x][0],ch[x][1]);
}
inline void Splay_push(int x)
{if(isroot(x))Splay_push(f[x]);pushdown(x);}
inline void rotate(int x){
    int y=f[x],z=f[y],k=chk(x),v=ch[x][!k];
    if(isroot(y))ch[z][chk(y)]=x;ch[x][!k]=y,ch[y][k]=v;
    if(v)f[v]=y;f[y]=x,f[x]=z;pushup(y);
}
inline void Splay(int x){
    int y=x;Splay_push(x);
    while(isroot(x)){
        if(isroot(y=f[x]))
           rotate((ch[y][0]==x)^(ch[f[y]][0]==y)?x:y);
        rotate(x); 
    }pushup(x);return;
}
inline void Access(int x){
    for(register int y=0;x;x=f[y=x])
       Splay(x),ch[x][1]=y,pushup(x); 
}
inline int findroot(int x){
    Access(x);Splay(x);
    while(ch[x][0])pushdown(x),x=ch[x][0];
    Splay(x);return x;
}
inline void makeroot(int x){Access(x);Splay(x);r[x]^=1;}
inline void split(int x,int y){makeroot(x);Access(y);Splay(y);}
inline void link(int x,int y){makeroot(x);if(findroot(x)!=findroot(y))f[x]=y;}
inline void cut(int x,int y){split(x,y);if(findroot(y)==x&&f[x]==y&&!ch[x][1])f[x]=ch[y][0]=0;}
int main(){
    IN(n),IN(m);
    for(register int x,y,i=1;i<n;++i)
    {IN(x),IN(y);link(x,y);}
    for(register int op,x,i=1;i<=m;++i){
        IN(op),IN(x);
        if(op==0){
            makeroot(x);v[x]^=1;pushup(x);
        }else if(op==1){
            split(1,x);
            if(!s[x]){printf("-1\n");continue;}
            while(s[x]){
                pushdown(x);
                if(s[ch[x][0]])x=ch[x][0];
                else if(v[x])break;
                else x=ch[x][1];
            }printf("%d\n",x);
        }
    }return 0;
}

本文标题:【题解】 Qtree3 LCT luoguP4116

文章作者:Qiuly

发布时间:2019年02月15日 - 00:00

最后更新:2019年03月29日 - 13:55

原始链接:http://qiulyblog.github.io/2019/02/15/[题解]luoguP4116/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。